#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N	20
#define MAX(a, b)	(a) > (b) ? (a) : (b)
#define MIN(a, b)	(a) < (b) ? (a) : (b)
#define SWAP(a, b) \
	do {\
		typeof(a) t;\
		t = (a);\
		(a) = (b);\
		(b) = t;\
	} while(0)

int main(void)
{
	int arr[N];
	int i, j;
	int t;
	int max, min, sum;
	float avg;

	srand(time(NULL));

	// 赋值 随机值
	for (i = 0; i < N; i++) {
		arr[i] = rand() % 1000;	
		printf("%d ", arr[i]);
	}
	printf("\n");

	// 选择排序
	// 排序:思路依次确定每一个位置对应的元素
	// i就是待确定的位置
	for (i = 0; i < N; i++) {
		// 找到应该放到i这个位置的元素,换过来
		min = i; // min是存放目前没有顺序的所有元素的最小值的下标
		for (j = i + 1; j < N; j++) {
			if (arr[j] < arr[min])
				min = j;
		}
		// min就是最小值的下标
		if (min != i) {
			t = arr[min];
			arr[min] = arr[i];	
			arr[i] = t;
		}
	}

	for (i = 0; i < N; i++)
		printf("%d ", arr[i]);
	printf("\n");

	// 冒泡排序 从大到小
	for (i = 0; i < N - 1; i++) {
		// 第i趟
		for (j = 0; j < N - i - 1; j++) {
			// j是第i趟要比较元素的下标值范围,每增加1趟,最大下标减少1个.
			// 冒泡相邻元素比较,也就是j和j+1,最大下标N - i - 1,j的最大值应该是N - i - 2
			if (arr[j] < arr[j+1]) {
				SWAP(arr[j], arr[j+1]);
			}
		}
	}

	printf("经过冒泡从大到小排序后\n");
	for (i = 0; i < N; i++)
		printf("%d ", arr[i]);
	printf("\n");

	// 直接插入排序 从小到大
	for (i = 1; i < N; i++) {
		// 下标为i的元素就是待插入的元素的下标值
		t = arr[i];
		for (j = i - 1; j >= 0; j--) {
			// 找到第一个比t小的元素的位置, 如果>t,往后挪
			if (t > arr[j])
				break; // t就是要放在j+1位置
			arr[j + 1] = arr[j];
		}
		// for终止有两种可能.1则break终止,找到了第一个比t小的元素,下标j.2则所有的元素都比t大,j < 0,j == -1,t应该放到j+1
		arr[j + 1] = t;
	}

	printf("经过直接插入从小到大排序后\n");
	for (i = 0; i < N; i++)
		printf("%d ", arr[i]);
	printf("\n");


#if 0
	// 假定第一个元素是最大 最小的
	sum = min = max = arr[0];
	for (i = 1; i < N; i++) {
		sum += arr[i]; // 求和
		max = MAX(max, arr[i]);
		min = MIN(min, arr[i]);
	}

	avg = (float)sum / N;
	printf("max:%d, min:%d, avg:%.2f\n", max, min, avg);
#endif	
	return 0;
}

